1. Field of the Invention
The present invention relates to an apparatus and method for efficiently computing a log likelihood ratio (LLR) using an improved maximum a posteriori (MAP) algorithm known as block combining.
2. Discussion of Related Art
The ongoing development of communication systems has generated demand for a high-speed channel coding method reliable for information transmission. However, information loss is caused by noise in a communication channel, fading, interference, and so on. In order to minimize such information loss and correct errors, an error correction code is indispensable. Ever since Shannon published the results of his research in 1948, error correction codes have been widely studied. One type of error correction code known as turbo code, suggested by Berrou, Glavieux and Thitimaishima in 1993, has excellent error correction performance approaching Shannon's limit and thus is being actively researched. Decoding of turbo code restores the original information by repetitive decoding using a MAP decoder or soft-output Viterbi algorithm (SOVA) decoder. In comparison with a SOVA algorithm, a MAP algorithm is more complex but has superior bit error rate (BER) performance and thus is widely used.
The MAP algorithm, first suggested by Bahl, et al. in 1974, calculates an a posteriori probability (APP) from a signal mixed with noise. The MAP decoding algorithm is aimed at determining information bits having the highest probability with respect to a received symbol after data is received. FIG. 1 is a 4-state trellis diagram from time (k−1) to time (k+1).
In FIG. 1, alpha (α) is called a forward state metric (FSM) and denotes a state metric for transition of information bits from state S′ before time (k−1) to state S after time k. Beta (β) is called a backward state metric (BSM), and a current beta value can be calculated by repeatedly using a beta value of a previous state after all information is received in the same way as alpha. Gamma (γ) is defined as a branch metric (BM).
In order to calculate an LLR, a gamma value is calculated using received data, and then an alpha value and a beta value are calculated using the calculated gamma value. In this process, Formulae 1-3 given below are used:
                                          α            k                    ⁡                      (            s            )                          =                              ∑                                          all                ⁢                _                ⁢                s                            ′                                ⁢                                                    γ                k                            ⁡                              (                                                      s                    ′                                    ,                  s                                )                                      ⁢                                          α                                  k                  -                  1                                            ⁡                              (                                  s                  ′                                )                                                                        Formula        ⁢                                  ⁢        1                                                      β                          k              -              1                                ⁡                      (                          s              ′                        )                          =                              ∑                                          all                ⁢                _                ⁢                s                            ′                                ⁢                                                    β                k                            ⁡                              (                s                )                                      ⁢                                          γ                k                            ⁡                              (                                                      s                    ′                                    ,                  s                                )                                                                        Formula        ⁢                                  ⁢        2                                          γ          k                                    s              ′                        ,            s                          =                  exp          ⁢                      {                                          2                                  σ                  2                                            ⁢                              (                                                                            x                      k                                        ⁢                                          u                      k                                                        +                                                            y                      k                                        ⁢                                          v                      k                                                                      )                                      }                                              Formula        ⁢                                  ⁢        3            
Here, Uk is a data bit and Vk is a parity bit. Xk is a data bit mixed with noise passed through a channel, and yk is a parity bit mixed with noise passed through a channel. When alpha, beta and gamma values are calculated, an LLR can be calculated using Formulae 4 and 5:
                              L          ⁡                      (                          u              k                        )                          =                  ln          ⁡                      (                                                            ∑                                                                                                                                          (                                                                                          s                                ′                                                            ,                              s                                                        )                                                    =                          >                                                                                                                                                                                          u                            k                                                    =                                                      +                            1                                                                                                                                              ⁢                                                                            α                                              k                        -                        1                                                              ⁡                                          (                                              s                        ′                                            )                                                        ⁢                                                            γ                      k                                        ⁡                                          (                                                                        s                          ′                                                ,                        s                                            )                                                        ⁢                                                            β                      k                                        ⁡                                          (                      s                      )                                                                                                                    ∑                                                                                                                                          (                                                                                          s                                ′                                                            ,                              s                                                        )                                                    =                          >                                                                                                                                                                                          u                            k                                                    =                                                      -                            1                                                                                                                                              ⁢                                                                            α                                              k                        -                        1                                                              ⁡                                          (                                              s                        ′                                            )                                                        ⁢                                                            γ                      k                                        ⁡                                          (                                                                        s                          ′                                                ,                        s                                            )                                                        ⁢                                                            β                      k                                        ⁡                                          (                      s                      )                                                                                            )                                              Formula        ⁢                                  ⁢        4                                          L          ⁡                      (                          u                              k                +                1                                      )                          =                  ln          ⁡                      (                                                            ∑                                                                                                                                          (                                                          s                              ,                                                              s                                ″                                                                                      )                                                    =                          >                                                                                                                                                                                          u                                                          k                              +                              1                                                                                =                                                      +                            1                                                                                                                                              ⁢                                                                            α                                              k                        -                        1                                                              ⁡                                          (                      s                      )                                                        ⁢                                                            γ                      k                                        ⁡                                          (                                              s                        ,                                                  s                          ″                                                                    )                                                        ⁢                                                            β                      k                                        ⁡                                          (                                              s                        ″                                            )                                                                                                                    ∑                                                                                                                                          (                                                          s                              ,                                                              s                                ″                                                                                      )                                                    =                          >                                                                                                                                                                                          u                                                          k                              +                              1                                                                                =                                                      -                            1                                                                                                                                              ⁢                                                                            α                                              k                        -                        1                                                              ⁡                                          (                      s                      )                                                        ⁢                                                            γ                      k                                        ⁡                                          (                                              s                        ,                                                  s                          ″                                                                    )                                                        ⁢                                                            β                      k                                        ⁡                                          (                                              s                        ″                                            )                                                                                            )                                              Formula        ⁢                                  ⁢        5            
Formulae 4 and 5 enable calculation of LLRs at time k and time (k+1), respectively. Using these formulae, information bits having the highest probability of transition from a previous state to a current state are determined.
However, the MAP algorithm described above requires a large memory size and a significant amount of calculation. Thus, the MAP algorithm imposes heavy restrictions on system design and drives up the cost of system building.
In order to solve the above problem of the MAP algorithm requiring a large memory size, a block processing algorithm has been suggested. The block processing algorithm is a MAP algorithm capable of more efficiently using a memory according to a principle described below.
FIG. 2 is a 4-state trellis diagram employing a block processing technique from time (k−1) to time (k+1) according to conventional art. The algorithm using the block processing technique calculates alpha values and beta values from time (k−1) to time (k+1), at time (k+1) rather than at time k. Thus, the algorithm can reduce the amount of memory required to store an alpha value and a beta value at time k in the middle of the process. Alpha and beta values are calculated by Formulae 6 to 8 given below:
                                          α                          k              +              1                                ⁡                      (            s            )                          =                              ∑                                          all                ⁢                _                ⁢                s                            ′                                ⁢                                    γ              ⁡                              (                                                      s                    ′                                    ,                  s                  ,                                      s                    ″                                                  )                                      ⁢                                          α                                  k                  -                  1                                            ⁡                              (                                  s                  ′                                )                                                                        Formula        ⁢                                  ⁢        6                                                      β                          k              -              1                                ⁡                      (                          s              ′                        )                          =                              ∑                                          all                ⁢                _                ⁢                s                            ″                                ⁢                                    γ              ⁡                              (                                                      s                    ″                                    ,                  s                  ,                                      s                    ′                                                  )                                      ⁢                                          β                                  k                  +                  1                                            ⁡                              (                                  s                  ″                                )                                                                        Formula        ⁢                                  ⁢        7                                          γ          ⁡                      (                                          s                ″                            ,              s              ,                              s                ′                                      )                          =                              γ            ⁡                          (                                                s                  ″                                ,                s                            )                                ⁢                      γ            ⁡                          (                              s                ,                                  s                  ′                                            )                                                          Formula        ⁢                                  ⁢        8            
The algorithm using the block processing technique reduces the number of data access operations by efficiently using a memory according to the conventional MAP algorithm, thereby reducing a required memory size and power. However, the algorithm performs more multiplication operations than the conventional MAP algorithm in LLR calculation, and thus decoding speed is reduced.